#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        // results表示的是以当前房间为结尾能偷到的最大金额
        int length = nums.size();
        if (length == 1) return nums[0];
        if (length == 2) return max(nums[0], nums[1]);
        vector<int> results(length, 0);
        results[0] = nums[0];
        results[1] = max(nums[0], nums[1]);

        
        for (size_t i = 2; i < length; i++)
        {
            results[i] = max(results[i-1], results[i-2] + nums[i]);
        }

        return results[length-1];
        
    }
};

int main(int argc, char* argv[]){

    vector<int> a = {1, 2, 3, 1};
    int result;
    Solution solver;
    result = solver.rob(a);

    return 0;
}